【剑指Offer I】37.序列化二叉树

题目

请实现两个函数，分别用来序列化和反序列化二叉树。

你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

解答

序列化一棵二叉树，也就是用一个字符串表示这棵树，同时能够从该字符串还原出这棵树。

所以序列化得到的二叉树必须含有足够的信息，不能仅仅是某种简单遍历的结果，而是应该在二叉树遍历时保留空节点的信息。

方法一 DFS 先序遍历

将一棵二叉树按照先序遍历的方式序列化成 "val (leftchild) (rightchild)" 。简单递归即可。

代码中使用了 stringstream ，利用了字符串流的特性。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (root == NULL) {
            return  "null";
        }
        return to_string(root->val) + " " + serialize(root->left) + " " + serialize(root->right);
    }
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        stringstream ss;
        ss << data;
        return helper(ss);
    }

    TreeNode* helper(stringstream& ss) {
        string tmp;
        ss >> tmp;
        if (tmp == "null") {
            return NULL;
        }
        TreeNode* root = new TreeNode(stoi(tmp));
        root->left = helper(ss);
        root->right = helper(ss);
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));

复杂度

• 时间复杂度 $O(N)$
• 空间复杂度 $O(N)$

方法一 BFS 层序遍历

将一棵二叉树逐层逐节点序列化成字符串，空节点用 "null" 表示。

注意这里的层序遍历必须把空节点也放入队列中。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (root == NULL) {
            return "[]";
        }
        string s = "[";
        queue<TreeNode*> q;
        q.push(root);
        int width = 1;
        TreeNode* t = new TreeNode(0);
        while (!q.empty()) {
            t = q.front();
            q.pop();
            if(t != NULL) {
                s += to_string(t->val);
                q.push(t->left);
                q.push(t->right);
            }
            else {
                s += "null";
            }
            s += ",";
        }
        return s.substr(0,s.length()-1)+"]";
    }
    //字符串转int
    int stoi(string s) {
        stringstream stream;//字符串流
        stream << s;
        int val;
        stream >> val;
        stream.clear();
        return val;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data == "[]"){
            return NULL;
        }
        vector<string> tr;
        string tmp = "";
        for (int i = 0; i < data.length(); ++ i) {    
            char c = data[i];
            if (c == '[') {
                continue;
            }
            else if (c == ',' || c == ']') { // 遇到终止符
                tr.push_back(tmp); // 将前一个节点的值保存
                tmp = "";
                if(c == ']'){
                    break;
                }
            }
            else{
                tmp += c; // 节点值可能是多位整数
            }
        }
        
        TreeNode* root = new TreeNode(stoi(tr[0]));
        int cnt = 1, size = tr.size();
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            TreeNode* t = q.front();
            q.pop();
            if(t != NULL){
                if (cnt < size && tr[cnt] == "null") {
                    t->left = NULL;
                }
                else {
                    t->left = new TreeNode(stoi(tr[cnt]));                   
                }
                ++ cnt;
                if (cnt < size && tr[cnt] == "null") {
                    t->right = NULL;
                }
                else {
                    t->right = new TreeNode(stoi(tr[cnt]));
                }
                ++ cnt;
                q.push(t->left);
                q.push(t->right);
            }
        }
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

复杂度

• 时间复杂度 $O(N)$
• 空间复杂度 $O(N)$